COCI/2009-2010/Contest #7 - 24.04.2010/bakice/bakice.2.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <vector>
   4 #include <cassert>
   5
   6 #define D(x) cout << #x " = " << (x) << endl
   7 using namespace std;
   8
   9 const int MAXN = 105;
  10
  11 int dist(int x1, int y1,    int x2, int y2){
  12   int dx = x1 - x2;
  13   int dy = y1 - y2;
  14   return dx * dx + dy * dy;
  15 }
  16
  17 char mat[MAXN][MAXN];
  18 typedef pair<int, int> point;
  19
  20 int rows, cols;
  21 vector<point> people, chairs;
  22
  23 int chairFor[MAXN];
  24 vector<int> peopleFor[MAXN];
  25
  26 int dist(int guy, int chair){
  27   return dist(people[guy].first, people[guy].second, chairs[chair].first, chairs[chair].second);
  28 }
  29
  30 int main(){
  31   cin >> rows >> cols;
  32   for (int i = 0; i < rows; ++i){
  33     for (int j = 0; j < cols; ++j){
  34       cin >> mat[i][j];
  35       if (mat[i][j] == 'X') people.push_back(point(i, j));
  36       if (mat[i][j] == 'L') chairs.push_back(point(i, j));
  37     }
  38   }
  39
  40   for (int i = 0; i < people.size(); ++i){
  41     chairFor[i] = -1;
  42   }
  43
  44   vector<pair<int, pair<int, int> > > options;
  45   for (int i = 0; i < people.size(); ++i){
  46     for (int j = 0; j < chairs.size(); ++j){
  47       options.push_back(make_pair(dist(i, j), make_pair(i, j)));
  48     }
  49   }
  50
  51   sort(options.begin(), options.end());
  52   for (int k = 0; k < options.size(); ++k){
  53     int d = options[k].first;
  54     int guy = options[k].second.first;
  55     int chair = options[k].second.second;
  56     if (chairFor[guy] != -1) continue; //already seated
  57     if (peopleFor[chair].size() == 0 ||
  58         dist(peopleFor[chair][0], chair) == d){
  59       chairFor[guy] = chair;
  60       peopleFor[chair].push_back(guy);
  61     }
  62   }
  63
  64   // for (int i = 0; i < people.size(); ++i){
  65   //   D(chairFor[i]);
  66   // }
  67
  68   int ans = 0;
  69   for (int c = 0; c < chairs.size(); ++c){
  70     ans += (peopleFor[c].size() > 1);
  71   }
  72   cout << ans << endl;
  73   return 0;
  74 }